package leetcode.lcp0019;

public class Solution {
	public int minimumOperations(String leaves) {
		char[] cs = leaves.toCharArray();
		int len = cs.length;
		int[] irr = new int[len];// 不含当前i位置右侧都变红需要改变的次数
		for (int i = len - 2, sum = cs[len - 1] == 'r' ? 0 : 1; i >= 0; i--) {
			irr[i] = sum;
			sum += cs[i] == 'r' ? 0 : 1;
		}
		int rri = cs[0] == 'r' ? 0 : 1;// 不含当前i位置左侧变成全红需要的次数
		int ryy = rri;// 变成rrryyy形式需要的次数
		int ans = Integer.MAX_VALUE;
		for (int i = 1; i < irr.length - 1; i++) {
			char c = cs[i];
			if (c == 'r') {
				ryy = Math.min(rri, ryy) + 1;// 左侧全红或者rrry都行，当前r要变成y，所以+1
			} else {
				ryy = Math.min(rri, ryy);// 左侧全红或者rry都行，当前也不需要变
				rri++;// 下一个位置左侧变成全红的话需要当前位置y变r，所以++
			}
			ans = Math.min(ans, ryy + irr[i]);// 最小的就是左侧rryyy右侧rrr，这个合计最小的时候
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.minimumOperations("yry");
	}
}
